COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00013 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A97.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 6, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
{\bf Theorem:}  There is no algorithm which for every program $x$ and 
datum $d$, determines whether or not $x$ halts when presented with $d$.

This theorem is a relative of the barber paradox.  The barber (a man)
in a certain town has a sign on his wall saying ``I shave those men, and only
those, who do not shave themselves.''  Is the sign true or false?  Surprisingly,
it must be false, because otherwise all answers to the question whether the barber
shaves himself are self-contradictory.

\item {(1)}  The barber shaves himself.  According to the sign he doesn't
shave himself.
\item{(2)}  The barber does not shave himself.  Then, according to the sign, he
does shave himself.

First we show that the theorem is true for programming systems (like machine
language) where the program can act on itself, perhaps by making a copy of
itself and working on that.  Suppose we have a procedure $h(x,d)$ which yields
True if program $x$ halts on datum $d$, and False if $x$ runs forever on
datum $d$; notice that $h$ itself halts on all inputs.

Design a program which does this:

\item {(1)}  It reads its input datum to a variable $d$.
\item {(2)}  It makes a copy of itself, which we will call $p$.
\item {(3)}  It executes $h(p,d)$ to determine whether it is supposed to 
halt or not.
\item {(4)}  If the result $h(p,d)$ is True, it enters an infinite loop.
Otherwise it prints 0 and halts.

Like a barber, who can't be given an algorithm to apply to himself that
determines whether he shaves himself or not (if there were such an algorithm,
the barber could use it and then do the opposite of what it says he does),
a program, given an algorithm to test itself for stopping, can be designed
to do the opposite.

If the program is written in a system which, like Pascal, does not provide
for self-reference, we can get around that by letting it {\it read} a copy of
itself, decide whether it is supposed to stop or loop, and do the opposite.
The program will do the following:

\item {(1)}  It reads an input string into variable $p$.
\item {(2)}  It executes $h(p,p)$ to determine whether $p$ halts when given a
copy of itself as data or not.
\item{(3)}  If $h(p,p)$ is True, it enters an infinite loop; if False, it
prints 0 and stops.

If we had the procedure $h$, we could construct such a program.  Say the
program is the string $x$. Then present it with $x$ as input.  Two cases arise.

\item {(1)}  $h(x,x)$ is True.  Then Step 2 gets $h(p,p)$ = True, the program
enters a loop, and $h(x,x)$ should be False.
\item {(2)}  $h(x,x)$ is False.  Step 2 gets $h(p,p)$ = False, the program 
terminates, and $h(x,x)$ should be True.

Suppose we weaken the assumptions of the theorem.  Let $h(x,d)$ be a total
function, which if true guarantees that program $x$ halts on datum $d$, but if
False does not necessarily mean $x$ runs forever on datum $d$.  We build a program
$a$ to:

\item{(1)}  Read datum $d$
\item {(2)}  Execute $h(d,d)$
\item {(3)}  If $h(d,d)$ is True, print $U(d,d) + 1$.  Otherwise, print 0.

By our assumptions, program $a$ halts on all inputs.  If we execute program
$a$, presenting it with a copy of itself as its input datum, and $h(a,a)$ is True,
$a$ will print a result which is both $U(a,a)$ and $U(a,a) + 1$, a
contradiction.  Therefore $h(a,a)$ must be false.

So $a$ is a program which, we can readily see, always halts, but $h(a,a)$ can't
discover that.  No matter how clever an algorithm we devise to identify some
executions which halt, it is technically easy to find an execution which 
will halt but which our ``clever'' algorithm can't identify as halting.

Why can't algorithm $h$ do what we just did, and deduce that program $a$ halts
on all data?  That deduction depends on knowing that $h(x,d)$ always
halts, and that $h(x,d) =$ True implies that $U(x,d)$ halts.  In particular
cases, this knowledge may be unattainable.

In general, we may get into all the complications of self-reference and
self-modification even in a programming language that makes no explicit
provision for it.  Let a program $p$ read an input $x$, assumed to be a
program, and make a second ``working'' copy, $y:=x$.  It can then apply
arbitrary transformations $(y:=f(y)$ say) to $y$, and execute $x$ with $y$
as datum by evaluating $U(x,y)$.  If we then execute $p$, giving it a copy
of itself as its datum, the program it is modifying and executing is itself.

How about a program that belongs to a family of similar, but related, programs?
Can they be, not only self-referential, but ``each-other-referential''?
Easy.  Let each of programs $p↓1$ and $p↓2$ read data $x1$, and $x2$; the rest of
$p↓1$ and $p↓2$ is written on the assumption that, when the programs are executed,
$x1$ will contain a copy of $p↓2$.  Having written the programs, we can provide
copies on the input files, justifying the assumption.

Now, how about a whole infinite family of programs $p↓1,\, p↓2,\, p↓3,\ldots $?
Obviously $p↓1$ (say) can't refer to all of them unless there is some relation
among them, since only finitely many could be read in.  Let's say that each is a
special case of a program with one more parameter:
$$pi(x) = q(i,x)$$
We assume (the s-m-n theorem of recursive function theory) that, given a
program for $q$, a program for $p↓1$ can be constructed.  Now we write a
program which reads a datum into variable $q$, assumed to be the general
2-parameter that is wanted.  A specializing algorithm spec$(j,q)$ is presumably
available to get $pj$ from $q$ for any $j$.  By executing spec$(i,q)$ the
specialized program gets a copy itself.  It can get a copy of one of the
others, $pj$, by executing spec$(j,q)$.  When the (general) program is
written, a copy of it is provided as the datum to be read into $q$, and the
specializing value is provided to be read into $i$.

{\bf Example:}  To construct infinitely many different programs all of which,
on input $x$, print $x+1$.

General program:

{\obeylines\sfcode`;=3000 \parskip=0pt \parindent=20pt
{\bf read} $q$;\qquad (copy of the general program)
{\bf read} $i$; \qquad (specialized value, identifying $pi$)
{\bf for} $j:=1$ {\bf to} $i-1$ {\bf do}
\quad {\bf if} {\it spec}$(j,q)$ = {\it spec}$(i,q)$
\quad {\bf then while true do write(`help!')};
{\bf read X}; {\bf write} $(x+1)$.\par}

Notice that $p↓1$ never executes the {\bf for}-loop, so it reads $x$ and 
prints $x+1$.
Then $p↓2$ checks itself agains $p↓1$, and, if it finds $p↓1=p↓2$, $p↓2$ 
loops, which is not possible since $p↓1$ doesn't loop.
\bye